package com.cskaoyan.javase.recursion._1advantage;

/**
 * 递归的思想以及递归的优缺点
 * 引例：
 *      使用递归计算N（N>=1）的阶乘（factorial）
 *
 * n! = n * (n - 1) * (n - 2) * ... * 1;
 * 先使用循环求解阶乘,循环求解问题的思想是什么?
 * 用循环求解问题,最重要的找到循环体语句
 * n!这个循环,需要循环n次,循环进行累乘,每循环一次,每累乘一次,被乘数要减去1
 *
 * 用递归求解一个问题,怎么办呢?
 * 在使用递归求解时,需要在方法体中再次调用自身
 * n! = n * (n-1)!
 * (n-1)! = (n-1) * (n-2)!
 * ...
 * 2! = 2
 * 1! = 1
 * 这种将大问题分解为小问题的思想就是递归的思想：
 *      1.把一个复杂的大规模的问题，分解成若干相似的小规模的子问题。
 *          (递归体)
 *      2.当子问题规模足够小的时候，就可以直接得到小规模问题的解。
 *          (递归的出口)
 *      3.然后把所有的小规模的子问题的解，组合起来，得到要求解的大规模问题的解。
 *
 * 对比,得出递归的优缺点:
 * 优点:
 *      1.递归求解代码往往十分简洁(直观优点)
 *      2.递归求解问题的思路非常符合人类的思考习惯
 *          用递归求解一个复杂的问题
 *          往往更容易想得到.
 *
 * 缺点:
 *      1.栈溢出错误警告!它很危险,稍有不慎就会栈溢出
 *      2.递归求解的过程中存在大量的重复计算,这意味着递归求解问题的效率非常低
 *      并且递归求解时,要大量占用栈内存资源(如果递归用到了对象,也会占用堆内存空间)
 *      所以递归对资源的耗费也很大
 *      总之,递归求解问题的时间复杂度,空间复杂度都不优秀.
 *
 * 实际上,递归求解问题是计算机出现以后,利用了计算机的庞大算力,暴力求解问题的思路
 *
 * @since 11:05
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(factorialLoopSolution(16));
        System.out.println(factorialRecursionSolution(16));
    }

    // 用循环求解n的阶乘
    public static long factorialLoopSolution(int n) {
        long result = 1;
        int num = n;
        for (int i = 0; i < n; i++) {
            result *= num;
            num--;
        }
        return result;
    }

    public static long factorialRecursionSolution(int n) {
        // 递归的出口
        if (n == 1) {
            return 1;
        }
        // 递归体
        return n * factorialRecursionSolution(n - 1);
    }
}
